/*
 * @Description: In User Settings Edit
 * @Author: your name
 * @Date: 2019-08-21 09:08:45
 * @LastEditTime: 2019-08-22 08:34:06
 * @LastEditors: Please set LastEditors
 */
/*
 * @lc app=leetcode.cn id=14 lang=javascript
 *
 * [14] 最长公共前缀
 *
 * https://leetcode-cn.com/problems/longest-common-prefix/description/
 *
 * algorithms
 * Easy (34.44%)
 * Likes:    658
 * Dislikes: 0
 * Total Accepted:    109.4K
 * Total Submissions: 317.6K
 * Testcase Example:  '["flower","flow","flight"]'
 *
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 
 * 如果不存在公共前缀，返回空字符串 ""。
 * 
 * 示例 1:
 * 
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 
 * 
 * 示例 2:
 * 
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 
 * 
 * 说明:
 * 
 * 所有输入只包含小写字母 a-z 。
 * 
 */
/**
 * @param {string[]} strs
 * @return {string}
 */

//  水平扫描法
// var longestCommonPrefix = function(strs) {
//     if(strs.length == 0 ) return ""
//     var same_str = strs[0]
//     for(let i=0;i<strs.length;i++){
//         let j = 0
//         for(;j<same_str.length;j++){
//             if(same_str[j] != strs[i][j]){
//                 break
//             }
//         }
//         same_str = same_str.slice(0,j)
//         if(same_str == '') return ''
//     }
//     return same_str
// };



// 归并
var longestCommonPrefix = function(strs){
    if(strs.length == 0) return ''
    if(strs.length == 1) return strs[0]

    const middle = Math.floor(strs.length/2)
    const left_array = strs.slice(0,middle)
    const right_array = strs.slice(middle)

    return bj(longestCommonPrefix(left_array),longestCommonPrefix(right_array)) 
}

var bj = function(left,right){
    let i = 0;
    for(;i<left.length;i++){
        if(left[i] != right[i]) break
    }
    return left.slice(0,i)
}


// 二分
// var longestCommonPrefix = function(strs){
//     if(strs.length == 0) return ''
//     if(strs.length == 1) return strs[0]
//     // 取第一个为基准
//     const str = strs[0]
//     let start = 0
//     let end = str.length
//     let middle = 0 
//     let s_str = ''

//     while( start < end && end > middle){
//         middle = Math.ceil((end + start)/2)
//         ss_str = str.slice(0,middle)
//         // console.log(ss_str,middle)
//         let status = true
//         for(let i=1;i<strs.length;i++){
//             if(strs[i].indexOf(ss_str) != 0){
//                 status = false
//                 break
//             }
//         }
//         if(status){
//             start = middle
//             s_str = ss_str
//         }else{
//             end = middle
//         }
//     }
//     console.log(start,end,middle,s_str)
//     return s_str
// }

